package week_04;

/**
 * 面试题 04.06. 后继者
 * 设计一个算法，找出二叉搜索树中指定节点的“下一个”节点（也即中序后继）。
 * <p>
 * 如果指定节点没有对应的“下一个”节点，则返回null。
 */
public class InorderSuccessor_0406 {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        return findSucc(root, p);
    }

    public TreeNode findSucc(TreeNode root, TreeNode p) {
        TreeNode cur = root;
        TreeNode ans = null;
        // search到val的节点
        // cur 用来指向当前判断的节点
        while (cur != null) {
            // case2：当后继存在于经过的点中（找到一个>val的最小点）
            if (cur.val > p.val) {
                if (ans == null || ans.val > cur.val) {
                    ans = cur;
                }
            }
            // case1:找到p,存在右子树，返回右子的一路向左的叶子节点
            if (cur.val == p.val) {
                if (cur.right != null) {
                    cur = cur.right;
                    while (cur.left != null) {
                        cur = cur.left;
                    }
                    return cur;
                }
                break;
            }
            if (cur.val > p.val) {
                cur = cur.left;
            } else {
                cur = cur.right;
            }
        }
        // 如果没有右子树，返回遍历节点中最大的节点
        return ans;
    }

}
